#!/usr/bin/env python3

"""
A message containing letters from A-Z is beding encoded to numbers using the following mapping
'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.
"""

class Solution:
    def num_decodings(self, s):
        nums = [-1] * len(s)
        return self._num_decodings(s, 0, nums)

    def _num_decodings(self, s, start_index, cache):
        if cache[start_index] != -1:
            return cache[start_index]
        current_ch = s[start_index]
        result = None
        if current_ch == '0':
            result = 0
        if result is None:
            try:
                next_ch = s[start_index + 1]
            except IndexError:
                result = 1
        if result is None:
            num = self._num_decodings(s, start_index + 1, cache)
            two_ch_num = int(s[start_index : start_index + 2])
            if two_ch_num == 0 or two_ch_num > 26:
                result = num
            elif start_index + 3 > len(s):
                result = num + 1
            else:
                result = num + self._num_decodings(s, start_index + 2, cache)
        cache[start_index] = result
        return result
        


if __name__ == '__main__':
    s = Solution()

    assert 0 == s.num_decodings('01')
    assert 2 == s.num_decodings('12')
    assert 3 == s.num_decodings('226')
    
